# LeetCode 547. 省份数量
# https://leetcode.cn/problems/number-of-provinces/description/
from typing import List


class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        result = 0
        parents = [i for i in range(len(isConnected))]
        size = [1 for i in range(len(isConnected))]

        def find(x):
            if parents[x] != x:
                parents[x] = find(parents[x])
            return parents[x]

        def union(x, y):
            x = find(x)
            y = find(y)
            if x == y:
                return
            if size[x] < size[y]:
                x, y = y, x
            parents[y] = x
            size[x] = size[x] + size[y]

        for i in range(len(isConnected)):
            for j in range(i + 1, len(isConnected[0])):
                if isConnected[i][j] == 1:
                    union(i, j)

        for i in range(len(isConnected)):
            if parents[i] == i:
                result += 1
        return result


if __name__ == '__main__':
    # isConnected = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
    isConnected = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
    isConnected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 1], [1, 0, 1, 1]]
    print(Solution().findCircleNum(isConnected))
